#include "stdafx.h"
#include "graph.h"

using std::vector;


int * CGraph::BellmanFord( int u ) {

	int * d = new int[ cV ];
	vector< int > conseqs;
	int weight;


	for ( int i=0; i<cV; ++i ) {

		// uzupelnianie tablicy najkrotszych sciezek
		// wartosciami niezdefiniowanymi
		d[ i ] = INT_MAX / 2;
	}
	
	// z wierzcholka u do samego siebie
	// droga jest rowna 0
	d[ u - 1 ] = 0;
	
	int c_i;

	for( int i=0; i<cV-1; ++i ) {
	
		for( int j=0; j<cV; ++j ) {
		
			// wyszukanie nastepnikow wierzcholka ( j + 1 )
			// do ktorego prowadzi najkrotsza sciezka
			conseqs = GetConsequents( j + 1 );
			
			for (int i=0; i<conseqs.size(); ++i ) {
			
				c_i = conseqs[i];
				weight = GetWeight( j + 1, c_i );
				// sprawdzenie czy sciezka przez wierzcholek B
				// jest krotsza niz sicezka przez jeden z jego nastepnikow
				if( d[ c_i - 1 ] > d[ j ] + weight ) {
				
					// zaktualizowanie bierzacej tablicy najkrotszych sciezek
					d[ c_i - 1 ] = d[ j ] + weight;
				}
			}
		}
	}

	
	return d;
}